\subsection{Cosets}
Let \(H\) be a subgroup of some group \(G\), and let \(g \in G\).
Then a set of the form \(gH \coloneq \{ gh : h \in H \}\) is called a left coset of \(H\) in \(G\).
Also, a set of the form \(Hg \coloneq \{ hg : h \in H \}\) is called a right coset of \(H\) in \(G\).
Mostly we use left cosets, but right cosets can be seen in more specific scenarios.
Note that the order of group \(H\) is the same as the order of the cosets \(gH\) and \(Hg\); we can think of \(gH\) and \(Hg\) as translated copies of \(H\).
Note further that \(gH\) and \(Hg\) are not necessarily groups; in fact in general they are not groups.
We now consider some example cosets.
\begin{enumerate}
	\item Let \(H = \{ e \} \leq G\).
	      Then \(gH = \{ g \}\).
	\item Let \(H = 2\mathbb Z\) and let \(G = \mathbb Z\).
	      Then (where the cosets are written additively):
	      \begin{itemize}
		      \item \(0 + 2\mathbb Z = 2\mathbb Z\) which is the set of even integers.
		      \item \(1 + 2\mathbb Z = \{ 1 + k: k \in 2\mathbb Z \}\) which is the set of odd integers.
		      \item \(2 + 2\mathbb Z = 2\mathbb Z\).
		            There are only two distinct cosets of \(H\) in \(G\) here; every odd integer will create the set of odd integers, and every even integer will create the set of even integers.
	      \end{itemize}
	\item Let \(H = \{ e, (1\ 2) \}\), and let \(G = S_3\).
	      Then, each (left) coset of \(H\) in \(G\) is given by
	      \begin{itemize}
		      \item \(eH = \{ e, (1\ 2) \} = H\)
		      \item \((1\ 2)H = \{ (1\ 2), e \} = H\)
		      \item \((1\ 3)H = \{ (1\ 3), (1\ 2\ 3) \}\)
		      \item \((1\ 2\ 3)H = \{ (1\ 2\ 3), (1\ 3) \}\)
		      \item \((2\ 3)H = \{ (2\ 3), (1\ 3\ 2) \}\)
		      \item \((1\ 3\ 2)H = \{ (1\ 3\ 2), (2\ 3) \}\)
	      \end{itemize}
	      Note that:
	      \begin{itemize}
		      \item \(eH = H\)
		      \item \(\forall h \in H, hH = H\) as \(H\) is a group and therefore closed under multiplication with \(h\)
		      \item \(\abs{gH} = \abs{H}\)
		      \item \(\bigcup_{g\in G} gH = G\), and in this example in particular, each pair of cosets is equal and disjoint to any other pair
	      \end{itemize}
\end{enumerate}

\subsection{Lagrange's theorem}
\begin{definition}
	We define the index of a subgroup \(H \leq G\) in \(G\), written \(\abs{G : H}\), to be the number of distinct cosets of \(H\) in \(G\).
\end{definition}
\begin{theorem}[Lagrange's Theorem]
	Let \(H \leq G\) be a subgroup of a finite group \(G\).
	Then:
	\begin{enumerate}
		\item \(\abs{H} = \abs{gH}\) for any \(g \in G\);
		\item for any \(g_1, g_2 \in G\), either \(g_1 H = g_2 H\) or \(g_1 H \cap g_2 H = \varnothing\); and
		\item \(G = \bigcup_{g \in G} gH\)
	\end{enumerate}
	And in particular, \(\abs{G} = \abs{G : H} \cdot \abs{H}\).
\end{theorem}
\begin{proof}
	We prove each statement independently.
	\begin{enumerate}
		\item The function \(H \to gH\), defined by \(h \mapsto gh\), defines a bijection between \(H\) and \(gH\), so \(\abs{H} = \abs{gH}\).
		\item Suppose \(g_1 H \cap g_2 H \neq \varnothing\).
		      Then \(\exists g \in g_1 H \cap g_2 H\).
		      So \(g = g_1 h_1 = g_2 h_2\) for some \(h_1, h_2 \in H\).
		      So \(g_1 = g_2 h_2 h_1^{-1}\).
		      So for any \(h \in H\), we have
		      \[
			      g_1 h = g_2 \underbrace{h_2 h_1^{-1} h}_{\mathclap{\in H}}
		      \]
		      So certainly \(g_1 H \subseteq g_2 H\).
		      Employing a symmetric argument for the other way round, we have \(g_1 H = g_2 H\).
		\item Given some \(g \in G\) then \(g \in gH\), since \(e \in H\).
		      So \(G \subseteq \bigcup_{g \in G} gH\).
		      But also, \(gH \subseteq G\), so \(\bigcup_{g \in G} gH \subseteq G\).
		      So \(G = \bigcup_{g \in G} gH\).
	\end{enumerate}
	So now that we know that \(G\) is composed of a union of disjoint cosets, all of which are the same size, we know that \(\abs{G}\) is just the number of these cosets multiplied by the size of such a coset, or in other words
	\[
		\abs{G} = \abs{G : H} \cdot \abs{H}
	\]
\end{proof}
Note that we could equivalently have used right cosets in place of left cosets.
Remember that in general, \(gH \neq Hg\), and the set of left cosets is not equal to the set of right cosets.
\begin{proposition}
	\(g_1 H = g_2 H \iff g_1^{-1} g_2 \in H\).
\end{proposition}
\begin{proof}
	We first consider the forwards case.
	Clearly \(g_1\) is an element of \(g_1 H\), as \(H\) contains \(e\).
	Also, \(g_2\) is an element of \(g_2\).
	So \(g_1^{-1} g_2 \in H\).
	Now for the backwards case.
	Clearly, \(g_2 H\) contains the element \(g_2\), as \(e\) maps to it.
	Also, since \(H\) contains \(g_1^{-1} g_2\), \(g_1 H\) contains the element \(g_1 \ast (g_1^{-1} g_2) = g_2\).
	As cosets are either disjoint or equal, and they clearly share the element \(g_2\), then they are equal.
\end{proof}
Note further that \(g' \in gH\) implies \(g'H = gH\).
We may therefore take a single element from each of these distinct cosets, and we will call them \(g_1, g_2, \cdots, g_{\abs{G:H}}\).
Then
\[
	G = \bigsqcup_{i=1}^{\abs{G:H}} g_i H
\]
where the \(\bigsqcup\) symbol denotes a disjoint union of sets.
These \(g_i\) are called coset representatives of \(H\) in \(G\).

\begin{corollary}
	Let \(G\) be a finite group and \(g \in G\).
	Then \((\ord g) \mid \abs{G}\).
\end{corollary}
\begin{proof}
	Recall that \(\ord g\) is defined as the smallest \(n\) such that \(g^n = e\).
	We define the subgroup \(H \leq G\) as \(H = \genset g\).
	Then \(\ord g = \abs{H}\).
	By Lagrange's Theorem, we know that \(\abs{H} \mid \abs{G}\).
\end{proof}

\begin{corollary}
	Let \(G\) be a finite group, and let \(g \in G\).
	Then \(g^{\abs{G}} = e\).
\end{corollary}
\begin{proof}
	This follows directly from the previous corollary.
	\(g^{\abs{G}} = g^{n \cdot \ord g}\) for some natural number \(n\), so this simply reduces to \(e\).
\end{proof}

\begin{corollary}
	Groups of prime order are cyclic, and are generated by any non-identity element.
\end{corollary}
\begin{proof}
	Let \(\abs{G} = p\), where \(p\) is a prime.
	We will take some \(g \in G\), and generate a group from it.
	By Lagrange's Theorem, \(\abs{\genset{g}} \mid \abs{G}\), so \(\abs{\genset g}\) is either 1 or \(p\).
	Now, note that \(e\) and \(g\) are both elements of \(\genset{g}\), so if \(g \neq e\) then clearly \(\abs{\genset{g}} > 1\), so \(\abs{\genset{g}} = p\).
\end{proof}
We can take Lagrange's theorem into the world of number theory, and specifically modular arithmetic, where we are dealing with finite groups.
Clearly, \(\mathbb Z_n\) is a group under addition modulo \(n\), but what happens with multiplication modulo \(n\)?
Clearly this is not a group---for a start, 0 has no inverse.
By removing all elements of the group that have no inverse, we obtain \(\mathbb Z_n^*\).

Note that for any \(x \in \mathbb Z_n\), \(x\) has a multiplicative inverse if and only if \(\HCF(x, n) = 1\), i.e.\ if \(x\) and \(n\) are coprime.
This follows directly from the fact that we can write 1 as a linear combination of \(x\) and \(n\), i.e.\ \(xy + mn = 1\), thus defining \(y\) as the multiplicative inverse of \(x\) modulo \(n\).
From this, it is simple to check that \(\mathbb Z_n^*\) forms a group under multiplication.

We may also create an equivalent group-theoretic definition of Euler's totient function \(\varphi\) as follows: \(\varphi(n) \coloneq \abs{\mathbb Z_n^*}\).
We can now use Lagrange's theorem to prove the Fermat--Euler theorem (that is, \(\HCF(N, n) = 1 \implies N^{\varphi(n)} \equiv 1 \text{ mod } n\)) as follows.
\begin{proof}
	If \(N\) and \(n\) are coprime, then there is an element, here denoted \(a\), in \(\mathbb Z_n\) corresponding to \(N\).
	So \(a^{\varphi(n)} = a^{\abs{\mathbb Z_n^*}} = 1\) in \(\mathbb Z_n\).
	Since \(N = a + kn\), we may expand \(N^{\varphi(n)} = a^{\varphi(n)} + n(\cdots) \equiv a^{\varphi(n)} \equiv 1 \text{ mod } n\).
\end{proof}

\subsection{Groups of small order}
We can completely classify groups of small order; we already know enough to classify all groups up to order 5 using Lagrange's Theorem.
\begin{proposition}
	If \(\abs{G} = 4\), then \(G \cong C_4\) or \(G \cong C_2 \times C_2\).
\end{proposition}
\begin{proof}
	By Lagrange's Theorem, the possible orders of elements of \(G\) with \(\abs{G} = 4\) are 1 (only the identity), 2 and 4.
	\begin{itemize}
		\item If there is an element \(g\) of order 4, then \(G = \genset{G}\) because \(e \neq g \neq g^2 \neq g^3\), so it is cyclic of order 4.
		\item If there is no such element, then all non-identity elements must have order 2.
		      \(G\) is abelian (by question 7 on example sheet 1).
		      Take two distinct elements \(b, c\) of order 2.
		      Then:
		      \begin{itemize}
			      \item \(\genset b \cap \genset c = \{ e, b \} \cap \{ e, c \} = \{ e \}\)
			      \item \(bc = cb\) as the group is abelian.
			      \item The element \(bc\) is not equal to \(b\) or \(c\) (\(bc = b \implies c = e\) which is an element of order 1).
			            It is also not equal to \(e\) because then \(b = c^{-1}\) which implies \(b = c\).
			            So the remaining element of \(G\) is simply \(bc\).
			            So any element in \(G\) may be written as the product of an element in \(\genset b\) multiplied by an element in \(\genset c\).
		      \end{itemize}
		      These are the three conditions of the direct product theorem, so \(G = \genset b \times \genset c \cong C_2 \times C_2\).
	\end{itemize}
\end{proof}
Now here is a list the first five smallest groups (we need more tools in order to classify larger groups):
\begin{enumerate}
	\item \(G = \{ e \}\)
	\item \(G \cong C_2\) because a group of prime order is cyclic.
	\item \(G \cong C_3\) for the same reason.
	\item \(G \cong C_4\) or \(G \cong C_2 \times C_2\) by the proof above.
	\item \(G \cong C_5\) because 5 is prime.
\end{enumerate}
